/*
 * @lc app=leetcode.cn id=138 lang=java
 *
 * [138] 复制带随机指针的链表
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    //已经复制过的，缓存起来，防止出现环的时候，无限循环下去
    Map<Node,Node> copyedMap = new HashMap<Node,Node>();
    public Node copyRandomList(Node head) {
        if(null == head){
            return head;
        }

        if(copyedMap.containsKey(head)){
            return copyedMap.get(head);
        }
        Node copyHead = new Node(head.val);
        copyedMap.put(head,copyHead);

        copyHead.next = copyRandomList(head.next);
        copyHead.random = copyRandomList(head.random);

        return copyHead;
    }
}
// @lc code=end

